﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
/*
 * 
Say you factor 100: 1,2,4,5,10,20,25,50,100. The sum is 217. The prime factorization is 2*2*5*5. This function gives you [5*(5+1)+1]*[2*(2+1)+1] = [25+5+1]*[4+2+1] = 217

Factoring 8: 1,2,4,8. The sum is 15. The prime factorization is 2*2*2. This function gives you [2*(2*(2+1)+1)+1]=15

The algorithm boils down to (using Fi to mean the ith index of the factor F or F sub i):
 * 
 * http://www.spoj.pl/problems/CZ_PROB2/
 */
namespace CSharpAlgorithm
{
    class SumofFactors
    {
        public SumofFactors()
        {
            int t = Int32.Parse(TestConsole.ReadLine());
            while (t-- > 0)
            {
                int num = Int32.Parse(TestConsole.ReadLine());
                int topNumber = num / 2;
                long total = 1 + num;
                
                for (int i = 2; i < topNumber; i++)
                {
                    if (num % i == 0)
                    {
                        total += i + (num / i);
                    }
                    topNumber = num / i;
                }
                Console.WriteLine(total + ", " + topNumber);
            }
        }
    }
}
